// https://leetcode.cn/problems/word-search/
#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <algorithm>


using namespace std;

class Solution {
public:
	bool exist1(vector<vector<char>>& board, string word) {
        int row = board.size(), col = board[0].size();
        vector<vector<bool>> ex(row, vector<bool>(col, 0));
        pair<int,int> dir[4]={{0,1},{1,0},{-1,0},{0,-1}};
        bool t = 0;
        auto dfs = [&](auto&& me, int&& index, int x, int y){
            if(index == word.size()){
				t = 1;
				return;
			}
            if(x >= 0 && x < row 
			&& y >= 0 && y < col 
			&& !ex[x][y] 
			&& board[x][y] == word[index]
			){
                ex[x][y]=1;
                for(int i = 0; i != 4; ++i){                   
                    me(me, index+1, x+dir[i].first, y+dir[i].second);
                    if(t) return ;
                }
                ex[x][y]=0;
            }
        };
        int h = 0;
        for (const vector<char>& row : board){
            for (const char& c : row) {
				if (c == word[0])
				h += 1;
				else if (c == word.back())
				h -= 1;
			}
		}
        //剪枝，用少的那个。估计是可以剪掉那个刚好很多重复头元素的
        if (h > 0) reverse(word.begin(), word.end());
		
        for(int i = 0; i != row; ++i){
            for(int j = 0; j != col; ++j){
                if(board[i][j] == word[0]){
                    dfs(dfs, 0, i, j);
                    if(t)return t;
                }
            }
        }
        return 0;
    }

	
    bool exist(vector<vector<char>>& board, string word) {
		bool flag = false;
		int h = 0;
        for (const vector<char>& row : board){
            for (const char& c : row) {
				if (c == word[0])
				h += 1;
				else if (c == word.back())
				h -= 1;
			}
		}
        //剪枝，用少的那个。估计是可以剪掉那个刚好很多重复头元素的
        if (h > 0) reverse(word.begin(), word.end());
		
		int row = board.size();
		int col = board[0].size();
		vector<vector<int>>ex(row, vector<int>(col));
		
		auto bfs = [&](auto && bfs, int i, int j,int index, vector<vector<int>> ex){
			if(index == word.size() - 1){
				flag = true;
				return;
			}
			if(board[i][j] == word[index]){
				vector<pair<int, int>> directions = {{0,1},{0,-1},{-1,0},{1,0}};
				for(auto d : directions){
					int newI = i + d.first;
					int newJ = j + d.second;
					
					if(newI >= 0 && newI < board.size() && newJ >= 0 && newJ < board[0].size()){
						// cout << newI << " " << newJ << " " << board[newI][newJ] << endl;
						if(ex[newI][newJ] == 1 || board[newI][newJ] != word[index + 1]){
							continue;
						}
						ex[newI][newJ] = 1;
						bfs(bfs, newI, newJ, index + 1, ex);
						if(flag){
                            return;
                        }
						ex[newI][newJ] = 0;
					}
				}
				return;
			}
		};
		
		
		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				if(board[i][j] == word[0]){
					ex[i][j] = 1;
					bfs(bfs, board, i, j, 0, word, ex);
					ex[i][j] = 0;
					if(flag){
						return flag;
					}
				}
			}
		}
		return flag;
    }
	
	// void bfs(vector<vector<char>>& board, int i, int j,int index, string & word, vector<vector<bool>> ex){
		// if(index == word.size() - 1){
			// flag = true;
			// return;
		// }
		// if(board[i][j] == word[index]){
			// vector<pair<int, int>> directions = {{0,1},{0,-1},{-1,0},{1,0}};
			// for(auto d : directions){
				// int newI = i + d.first;
				// int newJ = j + d.second;
				
				// if(newI >= 0 && newI < board.size() && newJ >= 0 && newJ < board[0].size()){
					// // cout << newI << " " << newJ << " " << board[newI][newJ] << endl;
					// if(ex[newI][newJ] == 1 || board[newI][newJ] != word[index + 1]){
						// continue;
					// }
					// ex[newI][newJ] = 1;
					// bfs(board, newI, newJ, index + 1, word, ex);
					// ex[newI][newJ] = 0;
				// }
			// }
			// return;
		// }
	// }
	
	// bool check(vector<vector<char>>& board, string & word){
		// map<char, int>boardMap;
		// map<char, int>wordMap;
		// for(auto items : board){
			// for(auto item : items){
				// boardMap[item]++;
			// }
		// }
		// for(auto c : word){
			// wordMap[c]++;
			// cout << wordMap[c] << endl;
		// }
		// for(auto w : wordMap){
			// if(w.second > boardMap[w.first]){
				// return false;
			// }
		// }
		// return true;
	// }
};

int main(){
	Solution so;
	vector<vector<char>> s = {
		{'A','B','C','E'},
		{'S','F','E','S'},
		{'A','D','E','E'}};
	string t = "ABCESEEEFS";
	bool res = so.exist(s, t);
	if(res)
		cout << "find" << endl;
	else
		cout << "not" << endl;
	return 0;
}